﻿/*
题目: 使数组连续的最少操作数

给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。

如果 nums 满足以下条件，那么它是 连续的 ：

nums 中所有元素都是 互不相同 的。
nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。
比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。

请你返回使 nums 连续 的 最少 操作次数。

https://www.acwing.com/problem/content/9/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    // 去重 + 排序 + 二分
    // 最终元素一定都是 [x, x + (n - 1)] 的数据范围
    // 所以我们遍历每一个元素 nums[i], 寻找它的 nums[i] + (n - 1) 并统计需要补充的数目
    int minOperations(vector<int>& nums) {
        // 去重, unique 接受的容器需要是有序的
        int n = nums.size();
        ::sort(nums.begin(), nums.end());
        vector<int>::iterator after = std::unique(nums.begin(), nums.end());
        nums.resize(std::distance(nums.begin(), after));

        int res = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            int t = nums[i] + n - 1;
            int j = bsearch(nums, i, t);
            int need = 0;

            if (j == -1) {      // 没找到
                need = i + (n - nums.size());
            }
            else {
                if (nums[j] == t)       need = n - (j - i + 1);
                else /* nums[j] > t*/   need = n - (j - i);
            }

            res = min(res, need);
        }

        return res;
    }

    // 二分，找到第一个 >= t 的位置
    int bsearch(vector<int>& nums, int start, int t) {
        int left = start;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] >= t) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return left == nums.size() ? -1 : left;
    }
};
